今天要來介紹 B-tree key 的新增及刪除操作

insert key X into B-tree of order m

步驟如下：

1. 先 search X，並找到 X 該放的節點位置
2. 直接將 X 放入該節點中
3. 檢查該節點是否有 overflow，也就是 key 值超越上限。若沒有，則直接完成，若 overflow，則執行 Split
4. 分裂（split）：將第 ceiling(m / 2) 個 key 向上拉入 parent，原本的 node 則以他為基準，左右拆分成 2 個 node。
5. 因為將 1 個 key 拉入了 parent，因此需檢查 parent 是否 overflow（回到步驟 3），直到所有的 nodes 皆滿足 B-tree 定義。要注意的是，當在判斷 parent 時，完全不需要在乎他的 child，直到所有節點都滿足才將 child 連回 nodes。

看個案例：

delete key X in B-tree of order m

刪除鍵值的操作比較麻煩

1. 先 search，找到 X 所在的節點
2. 假設此節點為 Leaf，則先直接刪除 X，並判斷該點是否 underflow，也就是 key 值低於下限，若沒有，則直接完成。
3. 若節點 underflow，則先看左右距離 1 的 sibling，是否能夠借一個 key，也就是說，sibling 減少一個節點也不會 underflow，這種情況下，就執行 Rotation 操作
4. 若 sibling 減少一個節點會 underflow，那麼就執行 Combination 操作
5. 旋轉（Rotation）：屬於 Key 的重新分配，選擇 sibling 最靠近該節點的值拉上parent，拉上後，將其隔壁的 key 向下拉至 underflow 點。
   此時 underflow 點多一個 key，sibling 點少一個 key，parent key 數不變，因此沒人會 underflow，完成操作。
6. 合併（Combination）：將 sibling 中的所有 key，以及 parent 上的對應 key 拉下來合併，所謂對應 key 就是左右子點為 underflow node 和 sibling node 的 parent key。
   此時 parent 減少一個 key，因此需判斷 parent 是否 underflow（回到步驟 3），直到所有的 nodes 皆滿足 B-tree 定義。在判斷 parent 時，也不需要在乎他的 child，直到所有節點都滿足才將 child 連回 nodes。

一樣來個圖例：

總結

B-tree 到這邊就介紹完了，不過我們接下來會介紹他的變種：B+ Tree，是蠻多 DB 會採用的資料結構喔。